#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

#define FOR(i,a,n) for(int i=a,_n(n);i<_n;++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;
const int inf = 1<<29;
struct Edge
{
    int vs,vt,flow,cap;
    Edge *next;
    void set(int a,int b,int w,Edge* nt = NULL)
    {
    	vs=a,vt=b,cap=w;
    	flow=0; next= nt;
    }
    inline int remain()
    {
    	return cap-flow;
    }
};

class Graph
{
    static const int MVN=1010*2,MARCN= 200200*4+MVN*4;
public:
    int vn,arcn;
    Edge *edge,*head[MVN];
    Graph(int n=0)
    {
        init(n);
        edge=new Edge[MARCN];
    };
    void init(int n)
    {
        vn=n;
        arcn=0;
        fill(head,head+n+1,(Edge*)NULL);
    }
    void add(int vs,int vt,int cap)
    {
        edge[arcn].set(vs,vt,cap,head[vs]);
        head[vs]=&edge[arcn++];
    }
    void addEdge(int vs,int vt,int cap)
    {
    	add(vs,vt,cap);
    	add(vt,vs,0);
    }
    int maxFlow(int vs,int vt)
    {
        int dist[MVN],cnt[MVN],ans=0;
        Edge *pre[MVN],*cur[MVN];
        for(int i=0;i<=vn;i++)
        {
        	cnt[i]=dist[i]=0;
        	pre[i]=NULL;
        	cur[i]=head[i];
        }
        cnt[0]=vn;
        int pos=vs;
        Edge *ep;
        while (dist[vs]<vn)
        {
        	for(ep=cur[pos];ep;ep=ep->next) if(dist[pos]==dist[ep->vt]+1&&ep->remain()) break;
        	if(ep)
        	{
        		cur[pos]=ep; pre[ep->vt] = ep;
        		pos=ep->vt;
        		if(pos==vt)
        		{
        			int minf=inf;
        			for(ep=pre[vt];ep;ep=pre[ep->vs]) if(ep->remain()<minf)
        			{
        				minf=ep->remain();
        				pos=ep->vs;
        			}
        			for(ep=pre[vt];ep;ep=pre[ep->vs])
        			{
        				ep->flow+=minf;
        				edge[(ep-edge)^1].flow-=minf;
        			}
        			ans+=minf;
        		}
        	}
        	else
        	{
        		if(--cnt[dist[pos]]==0) break;
        		dist[pos]=vn;
        		for(ep=head[pos];ep;ep=ep->next) if(dist[pos]>dist[ep->vt]+1&&ep->remain())
        			dist[pos]=dist[ep->vt]+1,cur[pos]=ep;
				cnt[dist[pos]]++;
				if(pos!=vs) pos=pre[pos]->vs;
        	}
        }
        return ans;
    }
};

int a[1010];
int length[1010];
Graph g;
int main()
{
    int T;
    cin>>T;
    int n;
    while(T--)
    {
        cin>>n;
        g.init(n*2+10);
        int ss = n*2+4,tt=ss+1;
        REP(i,n) g.addEdge(i,i+n,1);
        REP(i,n) scanf("%d",a+i);
        int maxLength = -1;
        REP(i,n)
        {
            int tmax = 0;
            REP(j,i) if(a[j]<a[i]&&length[j]>tmax) tmax = length[j];
            length[i] = tmax+1;
            REP(j,i) if(a[j]<a[i]&&length[j]==tmax)
                g.addEdge(j+n,i,inf);
            maxLength = max(maxLength,length[i]);
        }
        REP(i,n)
        {
            if(length[i]==1) g.addEdge(ss,i,inf);
            if(length[i]==maxLength) g.addEdge(i+n,tt,inf);
        }
        cout<<g.maxFlow(ss,tt)<<endl;
    }
	return 0;
}
